1079. Letter Tile Possibilities.go

package leetcode

// 解法一 DFS
funcnumTilePossibilities(tilesstring) int {
m:=make(map[byte]int)
fori:=rangetiles {
m[tiles[i]]++
 }
arr:=make([]int, 0)
for_, v:=rangem {
arr=append(arr, v)
 }
returnnumTileDFS(arr)
}

funcnumTileDFS(arr []int) (rint) {
fori:=0; i<len(arr); i++ {
ifarr[i] ==0 {
continue
 }
r++
arr[i]--
r+=numTileDFS(arr)
arr[i]++
 }
return
}

// 解法二 DFS 暴力解法
funcnumTilePossibilities1(tilesstring) int {
res, tmp, tMap, used:=0, []byte{}, make(map[string]string, 0), make([]bool, len(tiles))
findTile([]byte(tiles), tmp, &used, 0, &res, tMap)
returnres
}

funcfindTile(tiles, tmp []byte, used*[]bool, indexint, res*int, tMapmap[string]string) {
flag:=true
for_, v:=range*used {
ifv==false {
flag=false
break
 }
 }
ifflag {
return
 }
fori:=0; i<len(tiles); i++ {
if (*used)[i] ==true {
continue
 }
tmp=append(tmp, tiles[i])
 (*used)[i] =true
if_, ok:=tMap[string(tmp)]; !ok {
//fmt.Printf("i = %v tiles = %v 找到了结果 = %v\n", i, string(tiles), string(tmp))
*res++
 }
tMap[string(tmp)] =string(tmp)

findTile([]byte(tiles), tmp, used, i+1, res, tMap)
tmp=tmp[:len(tmp)-1]
 (*used)[i] =false
 }
}